//
//  Problem1249.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/30.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1249. 移除无效的括号
 给你一个由 '('、')' 和小写字母组成的字符串 s。

 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

 请返回任意一个合法字符串。
 有效「括号字符串」应当符合以下 任意一条 要求：
     空字符串或只包含小写字母的字符串
     可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
     可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
  

 示例 1：
     输入：s = "lee(t(c)o)de)"
     输出："lee(t(c)o)de"
     解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
 示例 2：
     输入：s = "a)b(c)d"
     输出："ab(c)d"
 示例 3：
     输入：s = "))(("
     输出：""
     解释：空字符串也是有效的
 示例 4：
     输入：s = "(a(b(c)d)"
     输出："a(b(c)d)"
 提示：
     1 <= s.length <= 10^5
     s[i] 可能是 '('、')' 或英文小写字母
 */
@objcMembers class Problem1249: NSObject {
    
    func solution() {
        print(minRemoveToMakeValid("lee(t(c)o)de)"))
        print(minRemoveToMakeValid("a)b(c)d"))
        print(minRemoveToMakeValid("))(("))
        print(minRemoveToMakeValid("(a(b(c)d)"))
    }
    
    /*
     1: 创建一个字符数组charts,创建一个n计数
     2: 遍历字符串，遇到字母，放入数组中
     3: 遇到'(' 放入数组中, n++
     4: 遇到')'，如果n=0，跳过，n>0,放入数组中，n--
     5: 遍历完成后，n>0, 从后往前遍历，删除n个'('
     */
    func minRemoveToMakeValid(_ s: String) -> String {
        var charts:[Character] = []
        var n = 0
        for c in s {
            if c == "(" {
                charts.append(c)
                n += 1
            } else if c == ")" {
                if n > 0 {
                    charts.append(c)
                    n -= 1
                }
            } else {
                charts.append(c)
            }
        }
        
        var i = charts.count - 1
        while n > 0 {
            if charts[i] == "(" {
                charts.remove(at: i)
                n -= 1
            }
            i -= 1
        }
        
        return String(charts)
    }
}
